见到一道神题，学会两个知识点… 都是数学。

给出式子： max ⁡ ( S ) = ∑ T ⊂ S ( − 1 ) ∣ T ∣ + 1 min ⁡ ( T ) \max(S)=\sum_{T\sub S}(-1)^{|T|+1}\min(T) max(S)=T⊂S∑​(−1)∣T∣+1min(T) min ⁡ ( S ) = ∑ T ⊂ S ( − 1 ) ∣ T ∣ + 1 max ⁡ ( T ) \min(S)=\sum_{T\sub S}(-1)^{|T|+1}\max(T) min(S)=T⊂S∑​(−1)∣T∣+1max(T) 这里只给出第一个式子的证明，第二个式子的证明较为类似。 考虑最大值 max ⁡ ( S ) \max(S) max(S)，它成为最小值产生贡献当且近当 T = { max ⁡ ( S ) } T=\{\max(S)\} T={max(S)}，显然只会产生一次正贡献。 而对于不是最大值的元素 x ∈ S x\in S x∈S，设比它大的元素的个数为 k k k，那么它成为最小值产生贡献当且近当 T T T 为前 k k k 个元素的某个子集并上 { x } \{x\} {x}，那么它的系数就是： ∑ i = 0 k ( k i ) ( − 1 ) i \sum_{i=0}^k\binom{k}{i}(-1)^i i=0∑k​(ik​)(−1)i 二项式反演一下： ∑ i = 0 k ( k i ) ( − 1 ) i = ∑ i = 0 k ( k i ) ( − 1 ) i ( 1 ) k − i = ( 1 − 1 ) k = 0 \sum_{i=0}^k\binom{k}{i}(-1)^i=\sum_{i=0}^k\binom{k}{i}(-1)^i(1)^{k-i}=(1-1)^{k}=0 i=0∑k​(ik​)(−1)i=i=0∑k​(ik​)(−1)i(1)k−i=(1−1)k=0 所以所有不是最大值的元素的贡献都是0。 那么最后西格玛的结果就是 max ⁡ ( S ) \max(S) max(S)。

注意：这个式子当最小值不唯一的时候依然成立， min ⁡ ( T ) \min(T) min(T) 的含义就变为了所有并列最小值的和。但是所求的最大值必须唯一！

这个东西对于期望依然是成立的，也就是： E ( max ⁡ ( S ) ) = ∑ T ⊂ S ( − 1 ) ∣ T ∣ E ( min ⁡ ( T ) ) E(\max(S))=\sum_{T\sub S}(-1)^{|T|}E(\min(T)) E(max(S))=T⊂S∑​(−1)∣T∣E(min(T)) E ( min ⁡ ( S ) ) = ∑ T ⊂ S ( − 1 ) ∣ T ∣ E ( max ⁡ ( T ) ) E(\min(S))=\sum_{T\sub S}(-1)^{|T|}E(\max(T)) E(min(S))=T⊂S∑​(−1)∣T∣E(max(T)) 把定义从元素大小的求值改为期望的求值，完全不影响上面的证明过程，所以还是对的。

max ⁡ ( S ) k t h = ∑ T ⊂ S ( ∣ T ∣ − 1 k − 1 ) ( − 1 ) ∣ T ∣ − k min ⁡ ( T ) \max(S)_{kth}=\sum_{T\sub S}\binom{|T|-1}{{k-1}}(-1)^{|T|-k}\min(T) max(S)kth​=T⊂S∑​(k−1∣T∣−1​)(−1)∣T∣−kmin(T) 并不会证 还是挺好记的， k = 1 k=1 k=1的时候就退化成正常的min-max容斥了。

离散变量：值域不连续的变量。比如我们最常见的“求期望次数”，值域就是自然数。

给出一个离散变量 x x x，其分布概率满足： P ( x = k ) = ( 1 − p ) k − 1 p P(x=k)=(1-p)^{k-1}p P(x=k)=(1−p)k−1p 其中 p p p 是一个 [ 0 , 1 ] [0,1] [0,1] 的常量。 可以把 p p p 理解成做成某件事的概率，那么 P ( x = k ) P(x=k) P(x=k) 就是恰好用 k k k 次做成这件事的概率。

现在求这个变量的期望，也就是： ∑ i = 1 ∞ P ( x = i ) i \sum_{i=1}^{\infty}P(x=i)i i=1∑∞​P(x=i)i 设 q = 1 − p q=1-p q=1−p，那么我们就要求： ∑ i = 1 ∞ i × q i − 1 × ( 1 − q ) = ( 1 − q ) ∑ i = 1 ∞ i × q i − 1 \sum_{i=1}^{\infty}i\times q^{i-1}\times(1-q)=(1-q)\sum_{i=1}^{\infty}i\times q^{i-1} i=1∑∞​i×qi−1×(1−q)=(1−q)i=1∑∞​i×qi−1 设 s = ∑ i = 1 ∞ i × q i − 1 s=\sum_{i=1}^{\infty}i\times q^{i-1} s=∑i=1∞​i×qi−1，则有： q s − s = ∑ i = 1 ∞ ( i × q i ) − ∑ i = 1 ∞ ( i × q i − 1 ) qs-s=\sum_{i=1}^{\infty}(i\times q^{i})-\sum_{i=1}^{\infty}(i\times q^{i-1}) qs−s=i=1∑∞​(i×qi)−i=1∑∞​(i×qi−1) = ∑ i = 2 ∞ ( ( i − 1 ) × q i − 1 ) − ∑ i = 1 ∞ ( i × q i − 1 ) = − ∑ i = 1 ∞ q i − 1 = − 1 1 − q =\sum_{i=2}^{\infty}((i-1)\times q^{i-1})-\sum_{i=1}^{\infty}(i\times q^{i-1})=-\sum_{i=1}^{\infty}q^{i-1}=-\frac{1}{1-q} =i=2∑∞​((i−1)×qi−1)−i=1∑∞​(i×qi−1)=−i=1∑∞​qi−1=−1−q1​ 所以 s = − 1 ( 1 − q ) ( q − 1 ) s=-\frac{1}{(1-q)(q-1)} s=−(1−q)(q−1)1​ 所以原式就是： ∑ i = 1 ∞ i × q i − 1 × ( 1 − q ) = ( 1 − q ) s = − 1 q − 1 = 1 p \sum_{i=1}^{\infty}i\times q^{i-1}\times(1-q)=(1-q)s=-\frac{1}{q-1}=\frac{1}{p} i=1∑∞​i×qi−1×(1−q)=(1−q)s=−q−11​=p1​

还有一种更加阳间的证明方法： 回到现实意义： w w w 表示做成该件事的期望次数。 考虑做一次做成或者做不成，就有： w = p × 1 + ( 1 − p ) × ( w + 1 ) w=p \times1+(1-p)\times (w+1) w=p×1+(1−p)×(w+1) 移项，得： w = 1 p w=\frac{1}{p} w=p1​